package Util;

import java.io.Serializable;
import java.util.ArrayList;

public class Node2_3_4<T extends Comparable<T>> implements Serializable {

	/**
	 * 
	 */
	private static final long serialVersionUID = -4897830249855974902L;

	// container to keep data of Node
	private java.util.ArrayList<T> data;

	Node2_3_4<T> parent;
	private ArrayList<Node2_3_4<T>> children;

	// The order of my Tree, this is half of max children
	int HALF_MAX;

	// to draw
	// Point point;

	// when need create a new node, but a leaf node
	public Node2_3_4(int ordem, boolean leaf) 
	{
		this.HALF_MAX = ordem / 2;
		data = new java.util.ArrayList<T>((HALF_MAX * 2) - 1);
		if (!leaf) 
		{
			children = new java.util.ArrayList<Node2_3_4<T>>(HALF_MAX * 2);
		}
	}

	// create a new node but, is will be the rootNode
	public Node2_3_4(int ordem, Node2_3_4<T> currentRootNode) 
	{
		this(ordem, false);
		children.add(currentRootNode);
		splitChild(0, currentRootNode);
	}

	public int size() 
	{
		return data.size()+1;
	}
	
	public int ChildSize()
	{
		if(children == null)
			return 0;
		return children.size();		
	}

	public void add(T obj) 
	{
		Node2_3_4<T> node = this;
		while (!(node.isLeaf())) 
		{
			double d = node.indexOf(obj);
			int i = (int) d;
			if (i == d)			
				return;			
			else 
			{
				Node2_3_4<T> child = node.getChild(i);
				if (child.isFull())				
					node.splitChild(i, child);				
				else				
					node = child;				
			}
		}
		node.set(obj);
	}

	private void set(T obj) 
	{
		double pos = indexOf(obj);
		int rightPos = (int) pos;
		if (pos != rightPos) 
		{
			data.add(rightPos, obj);
			if (!isLeaf())
				children.add(rightPos + 1, null);
		}
	}

	/*
	 * private int CurrentPos() { for (int i = 0; i < data.size(); i++) { if
	 * (data.get(i) == null) return i - 1; } return -1;// data is clear }
	 */
	
	
	
	public boolean isLeaf() 
	{
		if (children == null)
			return true;
		return false;
	}

	public boolean isFull() 
	{
		return data.size() + 1 == HALF_MAX * 2 ? true : false;
	}

	//
	public boolean isMinimal() {
		return size() == HALF_MAX;
	}

	public double indexOf(T obj) 
	{
		for (int i = 0; i < data.size(); i++) 
		{
			if (data.get(i).compareTo(obj) == 0)
				return i;
			else if (data.get(i).compareTo(obj) > 0)
				return i + 0.5;
		}
		return size() - .5;// don't has a value > than obj
	}

	public T get(int index) {
		return data.get(index);
	}

	public boolean Contains(T obj) {
		return data.contains(obj);
	}

	public Node2_3_4<T> getChild(int index) {
		if (isLeaf())
			return null;
		else
			return children.get(index);
	}

	// when the node is full create a new node, right of original
	private Node2_3_4<T> createRightSibling() {
		// the brother
		Node2_3_4<T> sibling = new Node2_3_4<T>(HALF_MAX * 2, isLeaf());
		for (int i = HALF_MAX; i < (HALF_MAX * 2) - 1; i++)

			sibling.data.add(data.remove(HALF_MAX));// crazy :P

		if (!isLeaf()) {
			for (int i = HALF_MAX; i < HALF_MAX * 2; i++) {
				sibling.children.add(children.remove(HALF_MAX));
			}
		}
		return sibling;
	}

	protected void splitChild(int i, Node2_3_4<T> child) 
	{
		Node2_3_4<T> sibling = child.createRightSibling();
		set(child.data.remove(HALF_MAX - 1));
		children.set(i + 1, sibling);
	}

	/**
	 * Merge this node's ith and (i+1)th children (child and sibling, both
	 * minimal), moving the ith item down from this node. Delete sibling from
	 * disk.
	 */
	protected void mergeChildren(int i, Node2_3_4<T> child, Node2_3_4<T> sibling) {
		child.data.add(data.remove(i));
		children.remove(i + 1);
		if (!(child.isLeaf()))
			child.children.add(sibling.children.remove(0));
		for (int j = 0; j < HALF_MAX - 1; j++) {
			child.data.add(sibling.data.remove(0));
			if (!(child.isLeaf()))
				child.children.add(sibling.children.remove(0));
		}
	}

	// Remove date of that Node
	public void remove(T target) {
		double d = indexOf(target);
		int i = (int) d;
		if (isLeaf()) {
			if (i == d)
				data.remove(i);
		} else if (i == d)
			removeFromInternalNode(i, target);
		else
			removeFromChild(i, target);
	}

	protected void removeFromInternalNode(int i, T target) {
		Node2_3_4<T> child = getChild(i);
		Node2_3_4<T> sibling = getChild(i + 1);
		if (!(child.isMinimal()))
			data.set(i, (T) child.removeRightmost());
		else if (!(sibling.isMinimal()))
			data.set(i, (T) sibling.removeLeftmost());
		else {
			mergeChildren(i, child, sibling);
			child.remove(target);
		}
	}

	void removeFromChild(int i, T target) {
		Node2_3_4<T> child = getChild(i);
		if (child.isMinimal()) {
			if (i == 0) { // Target in first child
				Node2_3_4<T> sibling = getChild(1);
				if (sibling.isMinimal())
					mergeChildren(i, child, sibling);
				else
					rotateLeft(i, child, sibling);
			} else if (i == size() - 1) {
				// Target in last child
				Node2_3_4<T> sibling = getChild(i - 1);
				if (sibling.isMinimal()) {
					mergeChildren(i - 1, sibling, child);
					child = sibling;
				} else
					rotateRight(i - 1, sibling, child);
			} else {
				// Target in middle child
				Node2_3_4<T> rightSibling = getChild(i + 1);
				Node2_3_4<T> leftSibling = getChild(i - 1);
				if (!(rightSibling.isMinimal()))
					rotateLeft(i, child, rightSibling);
				else if (!(leftSibling.isMinimal()))
					rotateRight(i - 1, leftSibling, child);
				else
					mergeChildren(i, child, rightSibling);
			}
		}
		child.remove(target);
	}

	/**
	 * Remove and return the leftmost element in the leftmost descendant of this
	 * node. Write any modified nodes to disk.
	 */
	protected T removeLeftmost() {
		Node2_3_4<T> node = this;
		while (!(node.isLeaf())) {
			Node2_3_4<T> child = node.getChild(0);
			if (child.isMinimal()) {
				Node2_3_4<T> sibling = node.getChild(1);
				if (sibling.isMinimal()) {
					node.mergeChildren(0, child, sibling);
				} else {
					node.rotateLeft(0, child, sibling);
				}
			}
			return (T) child.removeLeftmost();
		}
		return (T) node.data.remove(0);
	}

	/**
	 * Remove and return the rightmost element in the rightmost descendant of
	 * this node. Write any modified nodes to disk.
	 */
	protected T removeRightmost() {
		Node2_3_4<T> node = this;
		while (!(node.isLeaf())) {
			Node2_3_4<T> child = node.getChild(size() - 1);
			if (child.isMinimal()) {
				Node2_3_4<T> sibling = node.getChild(size() - 2);
				if (sibling.isMinimal()) {
					node.mergeChildren(size() - 2, sibling, child);
					child = sibling;
				} else {
					node.rotateRight(size() - 2, sibling, child);
				}
			}
			return (T) child.removeRightmost();
		}
		return (T) node.data.remove(size() - 2);
	}

	/**
	 * Child is the ith child of this node, sibling the (i+1)th. Move one item
	 * from sibling up into this node, one from this node down into child. Pass
	 * one child from sibling to node. Write sibling to disk.
	 */
	protected void rotateLeft(int i, Node2_3_4<T> child, Node2_3_4<T> sibling) {
		child.data.add(data.get(i));
		if (!(child.isLeaf())) {
			child.children.add(sibling.children.remove(0));
		}
		data.set(i, (T) sibling.data.remove(0));
	}

	/**
	 * Sibling is the ith child of this node, child the (i+1)th. Move one item
	 * from sibling up into this node, one from this node down into child. Pass
	 * one child from sibling to node. Write sibling to disk.
	 */
	protected void rotateRight(int i, Node2_3_4<T> sibling, Node2_3_4<T> child) {
		child.data.add(0, data.get(i));
		if (!(child.isLeaf())) {
			child.children.add(0, sibling.children.remove(sibling.size() - 1));
		}
		data.set(i, (T) sibling.data.remove(sibling.size() - 2));
	}

}
